package DP;

public class 背包 {

    /**
     * 0-1背包问题， 给定一组物品，要求拿不超过  numLimit的物品， 取到最大的价值
     *
     * 定义  dp[i][weight]  表示拿第i件物品，重量为 weight 的时候的最大价值
     * @param weight
     * @param val
     * @return
     */
    private static int zeroOneBag(int[] weight, int[] val, int weightLimit, int numLimit) {
        int[][] dp = new int[numLimit+1][weightLimit+1];

        /**
         * for i in (1...N)    物品件数从1到N
         *  for j in (1...M)     重要要求从1到M
         */
        for (int i = 1; i <= numLimit; i++) {
            for (int j = 1; j <= weightLimit; j++) {
                if(j - weight[i-1] <0) {
                    //装不下
                    dp[i][j] = dp[i-1][j];
                }else {
                    dp[i][j] = Math.max(dp[i-1][j - weight[i-1]]+val[i-1], dp[i-1][j]);
                }

            }
        }
        return dp[numLimit][weightLimit];
    }


    public static void main(String[] args) {
        int[] weight = {2,1,3};
        int[] val = {4,2,3};
        int n = 3;   //最多装3件
        int m = 4;   //最多不超过4

        System.out.println(zeroOneBag(weight,val,m,n));;
    }
}
